import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 力扣：1046 最后一块石头的重量
 */
//超出时间限制
//class Solution {
//    public int lastStoneWeight(int[] stones) {
//        int len = stones.length - 1;
//       while(len > 1){
//           int x = 0;
//           int y = 0;
//           len = stones.length - 1;
//           Arrays.sort(stones);
//           //x<=y
//           x = stones[len - 1];
//           y = stones[len];
//           if (x == y){
//               len = len - 2;
//           }else {
//               stones[len - 1] = y - x;
//               len--;
//           }
//       }
//        return stones[0];
//    }
//}

class Solution8 {
    public int lastStoneWeight(int[] stones) {
        //最大堆
        //优先级队列

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int x:stones) {
            //最大堆
            priorityQueue.offer(x);
        }
        while (priorityQueue.size() > 1) {
            int a = priorityQueue.poll();
            int b = priorityQueue.poll();
            if (a > b) {
                priorityQueue.offer(a - b);
            }
        }
        //如果其为null，返回0
        return priorityQueue.isEmpty() ? 0 : priorityQueue.poll();

    }
}